package com.rui.shangXueTang.graph;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * @author : [锐神NO.3]
 * @version : [v1.0]
 * @className : Graph
 * @createTime : [2022/2/19 13:52]
 * @description : [描述该类的功能]
 */

@SuppressWarnings("all")
public class Graph {

    private ArrayList<String> vertextList;

    /**
     * 描述邻接矩阵
     */
    private int[][] edges;

    /**
     * 所有边的数量
     */
    private int edgesNum;

    private boolean[] isSelected;

    public Graph(int nodeNum){
        this.vertextList = new ArrayList<>();
        this.edges = new int[nodeNum][nodeNum];
        this.isSelected = new boolean[nodeNum];
    }

    /**
     * 插入顶点的方法
     */
    public void insertVertex(String vertex){
        this.vertextList.add(vertex);
    }

    /**
     * 添加图的边
     */
    public void insertEdges(int x, int y, int w){
        edges[x][y] = w;
        edges[y][x] = w;
        edgesNum++;
    }

    /**
     * 返回顶点的个数
     */
    public int getVertexSize(){
        return this.vertextList.size();
    }

    /**
     * 返回边的个数
     * @return
     */
    public int getEdgesNum(){
        return this.edgesNum;
    }

    /**
     * 获取顶点的权值
     */
    public int getWeight(int x, int y){
        return edges[x][y];
    }

    /**
     * 输出邻接矩阵图案
     */
    public void showList(){
        for(int i = 0 ; i < edges.length ; i++){
            for(int j = 0 ; j < edges[i].length; j++){
                System.out.print(edges[i][j] + "\t");
            }
            System.out.println("");
        }
    }

    /**
     * 给定一个索引位置，查到当前索引的第一个邻接点
     * 如果存在返回索引位置，如果不存在返回-1
     */
    public int getFirstVertex(int index){
        for(int i = 0 ; i < vertextList.size() ; i++){
            if(edges[index][i] != 0){
                return i;
            }
        }
        return -1;
    }

    /**
     * 根据给定的坐标，获取下一个邻接点
     */
    public int getNextVertex(int x, int y){
        for(int i = y + 1 ; i < vertextList.size() ; i++){
            if(edges[x][i] != 0){
                return i;
            }
        }
        return -1;
    }

    /**
     * 访问过的顶点
     */
    public String getValueIndex(int i){
        return this.vertextList.get(i);
    }

    /**
     * 深度优先算法
     */
    public void DFS(boolean[] isSelected, int index){
        System.out.print(getValueIndex(index) + "\t");

        //表示已经被访问过
        isSelected[index] = true;

        //获取第一个邻接点
        int w = getFirstVertex(index);

        //存在第一个临界点
        while(w != -1){
            if(!isSelected[w]){
                DFS(isSelected, w);
            }else {
                //被访问过了
                w = getNextVertex(index, w);
            }
        }
    }

    public void DFS(){
        for(int i = 0 ; i < getVertexSize() ; i++){
            if(!isSelected[i]){
                DFS(isSelected, i);
            }
        }
    }

    /**
     * 广度优先算法
     */
    public void BFS(boolean[] isSelected, int index){
        //取出头节点
        int u;

        //第一个邻接节点
        int w;

        //创建队列
        LinkedList<Integer> queue = new LinkedList<>();
        System.out.print(getValueIndex(index) + "\t");
        isSelected[index] = true;

        queue.addLast(index);

        while(!queue.isEmpty()){
            u = queue.removeFirst();
            w = getFirstVertex(u);
            while(w != -1){
                if(!isSelected[w]){
                    System.out.print(getValueIndex(w) + "\t");
                    isSelected[w] = true;
                    queue.addLast(w);
                }
                w = getNextVertex(u, w);
            }
        }
    }

    public void BFS(){
        for(int i = 0 ; i < getEdgesNum() ; i++){
            if(!isSelected[i]){
                BFS(isSelected, i);
            }
        }
    }
}
